package myself.a005Heap;

import myself.a000util.Constants;
import myself.a000util.Logarithm;

/**
 * @author 叶之越
 * Description
 * Date 2021/1/23
 * Time 22:15
 * Mail 739153436@qq.com
 */
public class HeapSort {

    public static void main(String[] args) {
        Logarithm.check(HeapSort.class, Constants.normalSort);
    }

    public void sort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }

        // 生成大根堆
        for (int i = arr.length - 1; i >= 0; i--) {
            heapify(arr, i, arr.length);
        }

        // 生成从小到大的数组
        int heapSize = arr.length;
        while (heapSize > 0) {
            swap(arr, 0, heapSize - 1);
            heapify(arr, 0, --heapSize);
        }
    }

    // 从底部往上插入
    public void heapInsert(int[] arr, int index) {
        // 在没有插到最低端的时候不要停止，但是我发现，如果index=0的时候下标的计算为 -1/2=0 ，仍然是不越界的，可以跳出循环
        while (arr[index] > arr[(index - 1) / 2]) {
            swap(arr, (index - 1) / 2, index);
            index = (index - 1) / 2;
        }

        // 我之前的写法，比较臃肿
        /*while (index > 0) {
            int father = (index - 1) / 2;
            if (arr[father] < arr[index]) {
                swap(arr, father, index);
                index =  (index - 1) / 2;
            }else {
                break;
            }
        }*/
    }

    public void heapify(int[] arr, int index, int heapSize) {
        int leftChild = index * 2 + 1;
        while (leftChild + 1 <= heapSize) {

            // 这个逻辑比较绕，和while循环里面条件有上下文关系
            int maxChild = leftChild + 2 <= heapSize && arr[leftChild + 1] >= arr[leftChild]
                    ? leftChild + 1 : leftChild;
            if (arr[index] < arr[maxChild]) {
                swap(arr, index, maxChild);
                index = maxChild;
                leftChild = index * 2 + 1;
            } else {
                break;
            }
        }
    }

    public void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}
